
        <html>
			<head>
			     <title>PHP自动化白盒审计技术与实现 - 路人甲</title>
				 <meta http-equiv="content-type" content="text/html; charset=UTF-8">
			</head>
			<body>
				<h1>原文地址:<a href="http://drops.wooyun.org/tips/6261">http://drops.wooyun.org/tips/6261</a></h1>
				
      <p>
        <h1>0x00 前言</h1>

<hr />

<p>国内公开的PHP自动化审计技术资料较少，相比之下，国外已经出现了比较优秀的自动化审计实现，比如RIPS是基于token流为基础进行一系列的代码分析。传统静态分析技术如数据流分析、污染传播分析应用于PHP这种动态脚本语言分析相对较少，但是却是实现白盒自动化技术中比较关键的技术点。今天笔者主要介绍一下最近的研究与实现成果，在此抛砖引玉，希望国内更多的安全研究人员将精力投入至PHP自动化审计技术这一有意义的领域中。</p>

<h1>0x01 基础知识</h1>

<hr />

<p>自动化审计的实现方式有多种，比如直接使用正则表达式规则库进行定位匹配，这种方法最简单，但是准确率是最低的。最可靠的思路是结合静态分析技术领域中的知识进行设计，一般静态分析安全工具的流程大多是下图的形式：</p>

<!--more-->

<p><img src="http://static.wooyun.org//drops/20150625/2015062502384893512.png" alt="" /></p>

<p>静态分析工作所要做的第一件事情就是将源码进行建模，通俗一点讲，就是将字符串的源码转为方便于我们后续漏洞分析的中间表示形式，即一组代表此代码的数据结构。建模工作中一般会采用编译技术领域中的方法，如词法分析生成token，生成抽象语法树，生成控制流程图等。建模工作的优劣，直接影响到后续污染传播分析和数据流分析的效果。</p>

<p>执行分析就是结合安全知识，对载入的代码进行漏洞分析和处理。最后，静态分析工具要生成判断结果，从而结束这一阶段的工作。</p>

<h1>0x02 实现思路</h1>

<hr />

<p>经过一段时间的努力，笔者和小伙伴也大致实现了一款针对自动化的静态分析工具。具体实现思路正是采用了静态分析技术，如果想深入了解实现思路，可以阅读之前发过的<a href="http://blog.csdn.net/u011721501/article/details/44982111">文章</a>。 在工具中，自动化审计流程如下：</p>

<p><img src="http://static.wooyun.org//drops/20150625/2015062502384998416.png" alt="" /></p>

<blockquote>
  <ul>
  <li><p>首先载入用户输入的待扫描的工程目录中所有的PHP文件，并对这些PHP文件做判别，如果扫描的PHP文件是Main file，即真正处理用户请求的PHP文件，那么对这种类型的文件进行漏洞分析。如果不是Main file类型，比如PHP工程中的类定义，工具函数定义文件，则跳过不做分析。</p></li>
  <li><p>其次进行全局数据的搜集，重点搜集的信息有待扫描的工程中类信息的定义，如类所在的文件路径、类中的属性、类中的方法以及参数等信息。同时对每个文件生成文件摘要，文件摘要中重点搜集各个赋值语句的信息，以及赋值语句中相关变量的净化信息和编码信息。</p></li>
  <li><p>全局初始化之后，进行编译前端模块的相关工作，使用开源工具PHP-Parser对待分析的PHP代码进行抽象语法树（AST）的构建。在AST的基础上，使用CFG构建算法构建控制流图，并实时地生成基本块的摘要信息。</p></li>
  <li><p>编译前端的工作中，如果发现敏感函数的调用，就停下来进行污染传播分析，进行过程间分析、过程内分析，找到对应的污点数据。然后基于数据流分析过程中搜集的信息，进行净化信息和编码信息的判断，从而判断是否为漏洞代码。</p></li>
  </ul>
</blockquote>

<p>如果上一步是漏洞代码，则转入漏洞报告模块进行漏洞代码段的收集。其实现的基础是在系统环境中维护一个单例模式的结果集上下文对象，如果生成一条漏洞记录，则加入至结果集中。当整个扫描工程结果之后，使用Smarty将结果集输出到前端，前端做扫描结果的可视化。</p>

<h2>0x03 初始化工作</h2>

<hr />

<p>在真实的PHP审计中，遇到敏感函数的调用，比如<code>mysql_query</code>，我们就会不由自主地去手动分析第一个参数，看是否可控。事实上，很多CMS都会将一些数据库查询的方法进行封装，使得调用方便且程序逻辑清晰，比如封装为一个类MysqlDB。这时，在审计中我们就不会搜索<code>mysql_query</code>关键字了，而是去找比如<code>db-&gt;getOne</code>这种类的调用。</p>

<p>那么问题来了，在自动化程序进行分析的时候，如何获知db->getOne函数是个数据库的访问类方法呢？</p>

<p>这就需要在自动化分析的初期就要对整个工程的所有类与定义的方法进行搜集，以便于程序在分析的时候寻找需要跟进的方法体。</p>

<p>对于类信息和方法信息的搜集，应该作为框架初始化的一部分完成，存储在单例上下文中：</p>

<p><img src="http://static.wooyun.org//drops/20150625/2015062502384944528.png" alt="" /></p>

<p>同时，需要识别分析的PHP文件是否是真正处理用户请求的文件，因为有些CMS中，一般会将封装好的类写入单独的文件中，比如将数据库操作类或者文件操作类封装到文件中。对于这些文件，进行污染传播分析是没有意义的，所以在框架初始化的时候需要进行识别，原理很简单，分析调用类型语句和定义类型语句的比例，根据阈值进行判别，错误率很小。</p>

<p>最后，对每个文件进行摘要操作，这一步的目的是为了后续分析时碰到require，include等语句时进行文件间分析使用。主要收集变量的赋值、变量的编码、变量的净化信息。</p>

<h1>0x04 用户函数处理</h1>

<hr />

<p>常见的web漏洞，一般都是由于危险参数用户可控导致的，这种漏洞称之为污点类型漏洞，比如常见的SQLI，XSS等。 PHP内置的一些函数本身是危险的，比如echo可能会造成反射型XSS。然而真实代码中，没人会直接调用一些内置的功能函数，而是进行再次封装，作为自定义的函数，比如：</p>

<pre><code>#!php
function myexec($cmd)
{
    exec($cmd) ;
}
</code></pre>

<p>在实现中，我们的处理流程是：</p>

<blockquote>
  <ul>
  <li><p>利用初始化中获取的上下文信息，定位到相应的方法代码段</p></li>
  <li><p>分析这个代码片段，查找到危险函数（这里是exec）</p></li>
  <li><p>定位危险函数中的危险参数（这里是cmd）</p></li>
  <li><p>如果在分析期间没有遇到净化信息，说明该参数可以进行传染，则映射到用户函数myexec的第一个参数cmd，并将这个用户自定义函数当做危险函数存放至上下文结构中</p></li>
  <li><p>递归返回，启动污点分析过程</p></li>
  </ul>
</blockquote>

<p>总结为一句话，我们就是跟入到相应的类方法、静态方法、函数中，从这些代码段中查询是否有危险函数和危险参数的调用，这些PHP内置的危险函数和参数位置都是放在配置文件中的进行配置完成的，如果这些函数和参数一旦被发现，且判断危险参数并没有被过滤，则将该用户自定义函数作为用户自定义危险函数。一旦后续的分析中发现调用这些函数，则立即启动污点分析。</p>

<h1>0x05 处理变量的净化和编码</h1>

<hr />

<p>在真实的审计过程中，一旦发现危险参数是可控的，我们就会迫不及待地去寻找看程序员有没有对该变量进行有效的过滤或者编码，由此判断是否存在漏洞。 自动化审计中，也是遵循这个思路。在实现中，首先要对每一个PHP中的安全函数进行统计和配置，在程序分析时，对每一条数据流信息，都应该进行回溯收集必要的净化和编码信息，比如:</p>

<pre><code>#!php
$a = $_GET['a'] ;
$a = intval($a) ;
echo $a ;
$a = htmlspecialchars($a) ;
mysql_query($a) ;
</code></pre>

<p>上面的代码片段看起来有些怪异，但只是作为演示使用。从代码片段可以看出，变量a经过了intval和htmlspecialchars两个净化处理，根据配置文件，我们顺利的收集到了这些信息。这时，要进行一次回溯，目的是将当前代码行向上的净化和编码信息进行归并。 比如在第三行时，变量a的净化信息只有一条intval，但是第五行时，要求将变量a的净化信息归并，收集为一个list集合intval和htmlspecialchars，方法就是收集到前驱代码中的所有数据流的信息，并进行回溯。</p>

<p><img src="http://static.wooyun.org//drops/20150625/2015062502384927913.png" alt="" /></p>

<p>细节部分是，当用户同时对同一个变量调用了如base64&#95;encode和base64&#95;decode两个函数，那么这个变量的base64编码会被消除。同样，如果同时进行转义和反转义也要进行消除。但是如果调用顺序不对或者只进行了decode，那么你懂的，相当危险。</p>

<h1>0x06 变量回溯和污点分析</h1>

<hr />

<h3>1、变量回溯</h3>

<hr />

<p>为了寻找出所有的危险sink点的参数（traceSymbol），将向前回溯与当前Block相连的所有的基本块，具体过程如下：</p>

<blockquote>
  <ul>
  <li><p>循环当前基本块的所有入口边，查找没有经过净化的traceSymbol并且查找基本块DataFlow属性中，traceSymbol的名字。</p></li>
  <li><p>如果一旦找到，那么就替换成映射的symbol，并且将该符号的所有净化信息和编码信息都复制过来。然后，追踪会在所有的入口边上进行。</p></li>
  <li><p>最后，CFG上不同路径上的结果会返回。</p></li>
  </ul>
</blockquote>

<p>当traceSymbol映射到了一个静态字符串、数字等类型的静态对象或者当前的基本块没有入口边时，算法就停止。如果traceSymbol是变量或者数组，就要检查是否在超全局数组中。</p>

<h3>2、污点分析</h3>

<hr />

<p>污点分析在过程间分析处理内置和用户定义函数过程中开始，如果程序分析时遇到了敏感的函数调用，则使用回溯或者从上下文中获取到危险参数节点，并开始进行污点分析。通俗讲，就是进行危险参数是否可能导致漏洞的判别。污点分析工作在代码<code>TaintAnalyser</code>中进行实现，获取到危险参数后，具体步骤如下：</p>

<blockquote>
  <ul>
  <li><p>首先，在当前基本块中寻找危险参数的赋值情况，寻找DataFlow的右边节点中是否存在用户输入source，比如$&#95;GET $&#95;POST等超全局数组。并使用不同类型漏洞判别的插件类判断这些节点是否是安全的。</p></li>
  <li><p>如果当前基本块中没有寻找到source，则进入本文件多基本块间分析过程。首先获取当前基本块的所有前驱基本块，其中前驱基本块中包含平行结构（if-else if-else），或者非平行结构（普通语句）。并进行危险变量分析，如果当前循环的基本块中没有前驱节点，则分析算法结束。</p></li>
  <li><p>如果基本块间分析没有找到漏洞，则进行最后的文件间分析。载入当前基本块之前的包含文件摘要，遍历这些文件摘要做出判断。</p></li>
  <li><p>如果上述步骤中，出现漏洞，则进入漏洞报告模块。否则，系统继续往下进行代码分析。</p></li>
  </ul>
</blockquote>

<p><img src="http://static.wooyun.org//drops/20150625/2015062502385056629.png" alt="" /></p>

<h1>0x07 目前的效果</h1>

<hr />

<p><img src="http://static.wooyun.org//drops/20150625/2015062502385095172.png" alt="此处输入图片的描述" /></p>

<p>我们对<code>simple-log_v1.3.12</code>进行了测试性扫描，结果是：</p>

<pre><code>Total : 76 XSS : 3 SQLI : 62 INCLUDE : 5 FILE : 3 FILEAFFECT : 1
</code></pre>

<p>测试代码都是一些比较明显的漏洞，且没有使用MVC框架，什么字符截断吃掉转义符这种，目前的技术还真的支持不了，不过也是可以扫出一些了。从测试过程来看，bug层出不穷，主要是前期实现时，很多语法结构与测试用例没有考虑进去，加上算法几乎都是递归的，所以很容易就造成无限递归导致Apache跪掉。</p>

<p>所以目前的代码真的只能算是试验品，代码的健壮性需要无数次重构和大量的测试来实现，笔者已经没有太多时间维护。</p>

<h1>0x08 总结</h1>

<hr />

<p>静态分析领域中，很多安全研究人员都是做C/C++/反编译汇编等方向，目前脚本语言领域也急需技术力量投入进去，因为这是一件很有意义的事情。</p>

<p>回到坑上面来，笔者和小伙伴们的实现中，有个重大的问题就是不支持MVC框架。这些MVC如CI框架，数据流很难进行统一捕捉，因为框架封装度很高。所以针对不同的框架估计需要不同的分析方式。</p>

<p>目前的状况是，可以识别一些简单的漏洞，代码不够健壮存在诸多bug。</p>

<p>最后，<code>talk is cheap, show me the code</code>. 实现代码在<a href="https://github.com/OneSourceCat/phpvulhunter">github</a>上可以找到。</p>

<p>代码分享出来的目的是供有志于或者已经投身于该领域的安全研究人员进行研究与讨论，目前还达不到随便拿出一个CMS就能跑的效果，望大家不要有所幻想。</p>      </p>
    
			</body>
		</html>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          